#!/usr/bin/python
# Filename: ex_DSIntro_work_1_1.py

# calculate mth value in k level Fibonacci array


class Fibonacci:

    def __init__(self, level=2):
        self.level = level
        self.array = [0] * (self.level-1)
        self.array.append(1)
        self.next = 0
        for i in self.array:
            self.next += i

    def __getitem__(self, key):
        length = len(self.array)
        if key < length:
            return (self.array[key])
        elif key == length:
            return (self.next)
        else:
            while key >= length:
                self.array.append(self.next)
                # 0, 1, 2, 3, 4, 5, (6, 7, ...)
                # 0, 1, 1, 2, 3, 5, (8, 13, ...)
                # i = 6, key = 8, self.next = 8
                # self.next = 8 + 8 - 3, 3's pos is 4 = 6 - 2
                self.next = self.next + self.next - self.array[length-self.level]
                length += 1

    def print_array(self):
        print self.array


if __name__ == "__main__":
    f = Fibonacci(3)
    z = f[10]
    f.print_array()
